package com.leetcode.Offer;

import java.util.ArrayList;
import java.util.HashMap;

public class JZ35 {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node q = head;
        //map中存的是(原节点，拷贝节点)的一个映射
        HashMap<Node, Node> map = new HashMap<>();
        while (q != null) {
            map.put(q,new Node(q.val));
            q=q.next;
        }
        //将拷贝的新的节点组织成一个链表
        q = head;
        while (q != null) {
            map.get(q).next=map.get(q.next);
            map.get(q).random=map.get(q.random);
            q=q.next;
        }
        return map.get(head);
    }
}
